#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
    int minPathSum(vector<vector<int>> &grid)
    {
        vector<vector<int>> dp(grid.size(), vector<int>(grid[0].size(), -1));
        dp[grid.size() - 1][grid[0].size() - 1] = grid[grid.size() - 1][grid[0].size() - 1];
        int maxi = grid.size();
        int maxj = grid[0].size();
        for (int i = maxi - 2; i >= 0; i--)
            dp[i][maxj - 1] = grid[i][maxj - 1] + dp[i + 1][maxj - 1];
        for (int j = maxj - 2; j >= 0; j--)
            dp[maxi - 1][j] = grid[maxi - 1][j] + dp[maxi - 1][j + 1];
        return minVal(dp, grid, 0, 0);
    }

    int minVal(vector<vector<int>> &dp, vector<vector<int>> &grid, int i, int j)
    {
        if (dp[i][j] != -1)
        {
            return dp[i][j];
        }
        dp[i][j] = min(minVal(dp, grid, i + 1, j), minVal(dp, grid, i, j + 1)) + grid[i][j];
        return dp[i][j];
    }
};
int main()
{
    cout << "Code64" << endl;
    Solution s;
    vector<vector<int>> grid = {{1}};
    cout << s.minPathSum(grid) << endl;
    return 0;
}